package java_0305_heap_leetcode;

/**
 * 出现次数最多的前k个数
 * 给你一个整数数组nums和一个整数k,请你返回其中出现频率前k高的元素,你可以按任意顺序返回。
 * 1 <= nums.length <= 105
 * k的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 */

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 分析：
 *   注意，这个题目的大小关系不是元素值的大小，而是元素出现次数的大小
 * 思路：
 *   1.将数组中出现的元素以及出现的次数存储到Map中
 *   2.扫描Map集合（思考为何是扫描Map集合而不是扫描原数组）
 *    .将前k个频次最高的元素放入最小堆中，当整个集合扫描完毕，最小堆中就存储了前k个频次最高的元素
 *   3.将最小堆依次出队即可得到答案
 * 细节问题：
 *   考虑定义类来解决问题：定义Freq类{int k;(不重复的哪些元素) int times;（出现的次数）}
 *   优先级队列存储的类型就是Freq类。如果不定义这个类，优先级队列中元素就不好处理
 *   此时优先级队列需要传入比较器：因为此时大小关系不是元素值的大小，而是出现频次的大小
 */
public class Num347_TopKFrequent {
    //定义Freq类，内部包含每个不重复的元素及出现的次数
    //这里不定义比较器，让他实现Comparable接口,自己来实现一个大小关系
    private class Freq implements Comparable<Freq>{
        private int key;
        private int times;
        public Freq(int key, int times) {
            this.key = key;
            this.times = times;
        }
        @Override
        public int compareTo(Freq o) {
            return this.times-o.times;//出现的次数越多返回值越大
            // （又因为此时最小堆，小值优先出队，所以队最后剩的都是大的次数对应的值）
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret=new int[k];
        //1.先扫描原nums数组，将每个不重复元素以及其出现的次数给存储到Map中
        Map<Integer,Integer> map=new HashMap<>();
        for(int i:nums){
//            map.put(i,map.getOrDefault(i,0)+1);//i是key值。map.getOrDefault(key,val):如果k值存在，返回相应的val值，不存在，给它设置默认值
            if(map.containsKey(i)){
                //说明i已经在map中存在了，map.get取出对应的出现次数val再+1
                map.put(i,map.get(i)+1);
            }else{
                //i在map中不存在，i是第一次出现。将val存1，说明i现在出现一次了
                map.put(i,1);
            }
        }
        //2.扫描Map集合，将前k个出现频次最高的元素放入到优先级队列中
        Queue<Freq> queue=new PriorityQueue<>();
        //Freq类是Compare接口的子类（按times进行的比较），优先级队列是知道谁大谁小的
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            //依次取出键值对，存储到entry对象中
            if(queue.size()<k){
                //队列元素小于k，直接将new Freq这个对象入队，它的key值是entry.getKey()，val值是entry.getValue()
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else{
                //判断堆顶元素和当前元素的出现次数关系
                //如果当前元素的val比堆顶元素还小，一定不是要找的元素
                Freq freq=queue.peek();//获取堆顶元素
                if(entry.getValue()<freq.times){
                    continue;
                }else{
                    //此时堆顶元素小，将其出队
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        //次数优先级队列中就存储了出现次数最多的前k个Freq对象
        //将它们出队
        for (int i = 0; i < k; i++) {
            ret[i]=queue.poll().key;//出的是key值
        }
        return ret;
    }
}
